package mo.offer_special;

import java.util.Arrays;

public class L014 {

    public boolean checkInclusion(String s1, String s2) {
        int[] check = new int[26];
        int s1Length = s1.length();
        for (int i = 0; i < s1Length; i++) {
            check[s1.charAt(i)-'a']++;
        }

        int i = 0;
        while (i < s2.length()) {
            int[] sub = new int[26];
            for (int j = i; j < i + s1Length && j < s2.length(); j++) {
                if (check[s2.charAt(j)-'a'] == 0) {
                    break;
                } else {
                    sub[s2.charAt(j)-'a']++;
                }
            }
            boolean allSame = true;
            for (int j = 0; j < 26; j++) {
                if (check[j] != sub[j]) {
                    allSame = false;
                    break;
                }
            }
            if (allSame) {
                return true;
            }
            i++;
        }
        return false;
    }


    //优化：滑动窗口，字符串2不需要重复计算
    public boolean checkInclusion2(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        int[] c1 = new int[26];
        int[] c2 = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            c1[s1.charAt(i)-'a']++;
            c2[s2.charAt(i)-'a']++;
        }
        if (Arrays.equals(c1, c2)) {
            return true;
        }
        int left = 0;
        int right = s1.length();
        while (right < s2.length()) {
            c2[s2.charAt(right)-'a']++;
            c2[s2.charAt(left)-'a']--;
            if (Arrays.equals(c1, c2)) {
                return true;
            }
            right++;
            left++;
        }
        return false;
    }


    public static void main(String[] args) {
        L014 test = new L014();
        System.out.println(test.checkInclusion("ab", "eidboaoo"));
    }

}
